#include <stdio.h>
// 找零问题，求最少找零数（局部最优）

// 贪心算法能快速找到局部最优解，但不能保证全局最优
int changeCount(int *arr,int n,int amount){
    int count = 0;
    while (amount!=0){
        for(int i=0;i<n;i++){
            if(amount>=arr[i]){
                amount-=arr[i];
                count++;
                break;
            }
        }
    }
    return count;
}


int main(){
    int amount = 66; // 应找零的金额
    int arr[] = {100,50,20,10,5,1}; // 面额
    int n = sizeof(arr)/sizeof(arr[0]);
    int count = changeCount(arr,n,amount); // 钱币数

    printf("Minimum number of currencies: %d",count);


    return 0;
}